package answer

import (
	"sort"
)

var (
	//初始化字符map对应的数字
	letterMap = map[int]string{
		1:    "I",
		4:    "IV",
		5:    "V",
		9:    "IX",
		10:   "X",
		40:   "XL",
		50:   "L",
		90:   "XC",
		100:  "C",
		400:  "CD",
		500:  "D",
		900:  "CM",
		1000: "M",
	}
)

func intToRoman(num int) string {
	result := ""
	nums := make([]int, 0)
	for key := range letterMap {
		nums = append(nums, key)
	}
	sort.Ints(nums)
	for num > 0 {
		//二分找到右边界
		index := sort.SearchInts(nums, num)
		if index < 1 {
			index = 0
		}
		if (index >= len(letterMap)) || (index > 0 && nums[index] != num) {
			index = index - 1
		}
		//使用+号比下面快
		result += letterMap[nums[index]]
		//result = fmt.Sprintf("%s%s", result, letterMap[nums[index]])
		num -= nums[index]
	}
	return result
}
